LInteger, LMath, or Monty
classes.
LInteger class.
Methods which operate on magnitudes must have these
magnitudes stored in exactly the same format described
for magnitudes in the LInteger class. An exception
to this rule is that lead zeros are ok here, except
where noted otherwise.
See the
magnitude section of the
internal representation section for details.
BMath
class work:
start, rippling a carry
works as given by the following pseudo-code:
set carry flag;
unsigned int* mem=start;
while (carry flag)
{
(*mem)++;
if (overflow)
set carry flag;
else
clear carry flag;
mem--;
}
start, rippling a borrow works
as given by the following pseudo-code:
set borrow flag;
unsigned int* mem=start;
while (borrow flag)
{
(*mem)--;
if (borrow)
set borrow flag;
else
clear borrow flag;
mem--;
}
static inline char BMath::GreaterThanOrEqualTo(const
unsigned int* A, const unsigned int* B, const int size)
Compares two magnitudes, returning
1 if the magnitude pointed to by A is greater than or
equal to
the magnitude pointed to by B and 0 otherwise.
A and B must have the same number of
digits. This number is specified by size.
static inline void BMath::BasicAdd(const unsigned int* A,
const unsigned int* B, unsigned int* C, const int size,
char& carry)
Adds the magnitude pointed to by A to the mangitude
pointed to by B, and stores the size least
significant
digits of the result into the memory segment pointed
to by C. If the addition results in a carry,
carry is set to 1, otherwise it is set to 0.
A and B must have the same number of
digits. This number is specified by size.
static void BMath::Add(const unsigned int* A, const unsigned int* B,
unsigned int* C, const int sizeOfA, const int sizeOfB, char& carry)
Adds the sizeOfB digit mangitude pointed to by
B to the sizeOfA digit mangitude point to
by A. The magnitude pointed to by A must have
at least as many digits as the magnitude pointed by B
for this to work. The sizeOfA least
significant digits of the sum are stored into memory starting at the
location pointed to by C. If the sum is a
sizeOfA+1 digit number, carry is set
to 1, otherwise it is set to 0.
static inline void BMath::RippleAdd(const unsigned int* A,
const unsigned int* B, unsigned int* C, const int size)
Adds the magnitude pointed to by A to the mangitude
pointed to by B, and stores the size
least significant
digits of the result into the memory segment pointed
to by C. If the addition results in a carry,
it is rippled as described in the
ripple carry algorithm with a start
point equal to C-1.
A and B must have the same number of
digits. This number is specified by size.
static inline void BMath::BasicSubtract(const unsigned int* A,
const unsigned int* B, unsigned int* C, const int size, char& borrow)
Subtracts the magnitude pointed to by B from the mangitude
pointed to by B, and stores size least
significant
digits of the result into the memory segment pointed
to by C. If the subtraction requires a borrow,
borrow is set to 1, otherwise it is set to 0.
A and B must have the same number of
digits. This number is specified by size.
static void BMath::Subtract(const unsigned int* A,
const unsigned int* B, unsigned int* C, const int sizeOfA,
const int sizeOfB)
Subtracts the sizeOfA digit magnitude pointed to by
B from the sizeOfB digit mangitude
pointed to by B, and stores the sizeOfA
least significant digits of the result into memory starting at the
address pointed to by C. The magnitude poitned to by
A must be greater than or equal to the magnitude
to by B and must have at least as many digits for this
method to work.
static inline void BMath::RippleSubtract(const unsigned int* A,
const unsigned int* B, unsigned int* C, const int size)
Subtracts the magnitude pointed to by B from the mangitude
pointed to by A, and stores size least
significant
digits of the magnitude of the result into the
memory segment pointed to by C. If the subtraction requires
in a borrow, it is rippled as descirbed in the
ripple borrow algorithm with a
start point equal to C-1.
A and B must have the same number of
digits. This number is specified by size.
static inline void BMath::Increment(unsigned int* linteger,
const int size, char& carry)
Icrements the size digit magnitude pointed to by
linteger by 1. If this increment result in
a carry, carry is set to 1, otherwise carry
is set to 0.
static inline void BMath::RippleIncrement(unsigned int* linteger,
const int size)
Icrements the size digit magnitude pointed to by
linteger by 1. If this increment result in
a carry, it is rippled out via the
ripple carry algorithm
with a start point equal to linteger-1.
static inline void BMath::RippleDecrement(unsigned int* linteger,
const int size)
Decrements the size digit magnitude pointed to by
linteger by 1. If this decrement results in
a borrow, it is rippled out via the
ripple borrow algorithm
with a start point equal to linteger-1.
static inline void BMath::BasicMultiply(const unsigned int* A,
unsigned int B, unsigned int* C, const int sizeA)
Multiplies the sizeA digit magnitude pointed to by
A by B and adds the
sizeA+1 digit result to the
sizeA+1 digit magnitude pointed at by C,
storing the lower sizeA+1 digits of the result in the
meomry location pointed to by C.
If this addition results in a carry it is rippled out via the
ripple carry algorithm
with a start point equal to C-1.
C must not be equal to A for this method
to work.
static inline void BMath::MultDouble(unsigned int* productBuf,
const unsigned int* a, const unsigned int* b)
Multplies the two digit magnitude pointed to by a
by the two digit magnitude pointed to by b.
The four digit result is stored starting at the memory location
pointed to by productbuf.
static inline void BMath::SquareDouble(unsigned int* productBuf,
const unsigned int* a)
Squares the two digit magnitude pointed to by a, and
stores the four digit starting at the memory location
pointed to by productbuf. This is method is
equivalent to
Mult64(productBuf,a,a), except that it is
a bit faster.
static void BMath::Multiply(const unsigned int* A, int sizeA,
const unsigned int* B, int sizeB, unsigned int* result)
Multiplies the sizeA digit magnitude pointed to by
A by the sizeB digit magnitude pointed
to by B and stores the sizeA+sizeB digit
result starting at the memory location pointed to by result.
In order for this to work, the memories locations from
result to result+sizeA+sizeB-1 inclusive must
be zero before this method is called.
static void BMath::Square(const unsigned int* a, const int sizeA,
unsigned int* result)
Squares the sizeA digit magnitude pointed to by
A and stores the 2*sizeA result
starting at the memory location pointed to by result.
In order for this to work, the memories locations from
result to result+2*sizeA-1 must be zero
before this method is called. This method is equivalent to
Multiply(a,sizeA,a,sizeA,result) except that it is
a bit faster.
static inline void BMath::BasicDivide(unsigned int dividendHigh,
unsigned int dividendLow, unsigned int divisor,
unsigned int& quotient, unsigned int& remainder)
Divides the two digit dividend given by
dividendHigh*base+dividendLow by divisor.
the quotient is stored in quotient and the
remainder is stored in remainder. (Shocking, huh? :) )
Be careful that the quotient can fit in an unsigned int
before calling this method, or you'll get a floating exception.
static void BMath::Divide(const unsigned int* divisor, const int divisorSize,
const unsigned int* dividend, const int dividendSize,
unsigned int*& quotient, unsigned int*& remainder)
Divides the dividendSize digit dividend by
the dividendSize digit divisor. Upon return,
quotient points to a dynamically allocated
memory block containing the
dividendSize-divisorSize+1 digit magnitude of the
quotient. remainder, on the other hand,
points to a dynamically allocated
memory block of dividendSize+1 digits,
the divisorSize least significant
of which will be magnitude of the
remainder, and the
dividendSize-divisorSize+1 most significant
of which will be zero.
The caller is assumed to own the memory pointed
to by quotient, and remainder
after this method is called, and, as such, is responsible for freeing it.
Warning:
The interface to this method will almost surely change
in the next version of this library so that the caller will be
responsible for allocating the dynamic memory to store the results
before calling the method.
Note:
dividendSize must be greater than or
equal to divisorSize for this method to work.
The magnitude pointed to by the divisor may not have lead zeros.
static inline int BMath::BSR(unsigned int x)
Returns the bit position (0-31, 0 being least significant) of
the most significant bit which is 1 in x.
static inline char BMath::Normalize(unsigned int* buf,
int size)
Shifts the bits of the size digit
magnitude pointed to by buf the minimum number
of digits left to bring a 1 into the most significant bit.
Zeros are brought in on the right.
The magnitude pointed to by buf must a least
one bit equal to 1 its most significant digit for this work.
The value returned is equal to the distance of the shift.
static inline void BMath::ShiftLeft(unsigned int* buf, int size, char distance)
Shifts the bits of the size
digit magnitude pointed to by buf left by the number of
positions given by the 5 least significant bits of
distance.
Zeros are shifted in on the right, while bits shifted out on the left
are lost.
static inline void BMath::ShiftRight(unsigned int* buf, int size, char distance)
Shifts the binary digits of the size
digit magnitude pointed to by buf right by the number of
positions given by the 5 least significant bits of
distance.
Zeros are shifted in on the left, while bits shifted out on the right
are lost.